{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d4e1489f",
   "metadata": {},
   "source": [
    "### 组队"
   ]
  },
  {
   "cell_type": "raw",
   "id": "b7312756",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，\n",
    "组成球队的首发阵容。\n",
    "每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1\n",
    "号位至 5 号位的评分之和最大可能是多少？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f23d04f9",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "with open('team.txt', 'r') as f:\n",
    "    content = f.read()\n",
    "    \n",
    "nums = content.split('\\n')[:-1]\n",
    "\n",
    "nums = [line.split(' ') for line in nums]\n",
    "\n",
    "nums = [[int(num) for num in line] for line in nums]\n",
    "\n",
    "nums = [sum(line) for line in nums]\n",
    "\n",
    "peoples = list()\n",
    "for i in range(5):\n",
    "    people = max(nums)\n",
    "    peoples.append(people)\n",
    "    nums.remove(people)\n",
    "    \n",
    "print(sum(peoples))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8653777f",
   "metadata": {},
   "source": [
    "### 年号字串"
   ]
  },
  {
   "cell_type": "raw",
   "id": "46642c0f",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "小明用字母 A 对应数字 1，B 对应 2，以此类推，用 Z 对应 26。对于 27\n",
    "以上的数字，小明用两位或更长位的字符串来对应，例如 AA 对应 27，AB 对 应 28，AZ 对应 52，LQ 对应 329。\n",
    "请问 2019 对应的字符串是什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05c914cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = 2019 % 26\n",
    "print(g)\n",
    "ans = 2019 - g\n",
    "while True:\n",
    "    ans = ans // 26\n",
    "    if ans > 26:\n",
    "        print(ans % 26)\n",
    "    else:\n",
    "        print(ans)\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdff6b94",
   "metadata": {},
   "source": [
    "### 数列求值"
   ]
  },
  {
   "cell_type": "raw",
   "id": "5b61f720",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求\n",
    "第 20190324 项的最后 4 位数字。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "475636bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "_1, _2, _3 = 1, 1, 1\n",
    "\n",
    "for i in range(3, 20190324):\n",
    "    _ = _1 + _2 + _3\n",
    "    _1 = _2\n",
    "    _2 = _3\n",
    "    _3 = _\n",
    "print(str(_3)[-4:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "240b4a84",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7b9072c0",
   "metadata": {},
   "source": [
    "### 数的分解"
   ]
  },
  {
   "cell_type": "raw",
   "id": "2a197c78",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包\n",
    "含数字 2 和 4，一共有多少种不同的分解方法？\n",
    "注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和\n",
    "1001+1000+18 被视为同一种。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "858ab824",
   "metadata": {},
   "source": [
    "### 迷宫"
   ]
  },
  {
   "cell_type": "raw",
   "id": "92a05c8a",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可\n",
    "以通行的地方。\n",
    "010000\n",
    "000100\n",
    "001001\n",
    "110000\n",
    "迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这\n",
    "个它的上、下、左、右四个方向之一。\n",
    "对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，\n",
    "一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。\n",
    "对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，\n",
    "其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。\n",
    "请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务\n",
    "必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt，\n",
    "内容与下面的文本相同）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fd30a39e",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('maze.txt', 'r') as f:\n",
    "    content = f.read()\n",
    "\n",
    "content = content.split('\\n')\n",
    "print(content)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6269f806",
   "metadata": {},
   "source": [
    "### 特别数的和"
   ]
  },
  {
   "cell_type": "raw",
   "id": "d0736a88",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到\n",
    "40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。\n",
    "请问，在 1 到 n 中，所有这样的数的和是多少？\n",
    "【输入格式】\n",
    "输入一行包含两个整数 n。\n",
    "【输出格式】\n",
    "输出一行，包含一个整数，表示满足条件的数的和。\n",
    "【样例输入】\n",
    "40\n",
    "【样例输出】\n",
    "574"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a56a68a",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = ['2', '0', '1', '9']\n",
    "\n",
    "n = int(input())\n",
    "\n",
    "results = list()\n",
    "for i in range(1, n+1):\n",
    "    string = list(str(i))\n",
    "    for char in string:\n",
    "        if char in arr:\n",
    "            results.append(i)\n",
    "            break\n",
    "            \n",
    "print(sum(results))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25d6bb10",
   "metadata": {},
   "source": [
    "### 完全二叉树的权值"
   ]
  },
  {
   "cell_type": "raw",
   "id": "be057cbe",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从\n",
    "上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：\n",
    "现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点\n",
    "权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。\n",
    "注：根的深度是 1。\n",
    "【输入格式】\n",
    "第一行包含一个整数 N。\n",
    "第二行包含 N 个整数 A1, A2, · · · AN 。\n",
    "【输出格式】\n",
    "输出一个整数代表答案。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7b4e6997",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "1 6 5 4 3 2 1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "N = int(input())\n",
    "\n",
    "nums = list(map(int, input().split()))\n",
    "\n",
    "i = 1\n",
    "count = list()\n",
    "while True:\n",
    "    count.append(i)\n",
    "    i *= 2\n",
    "    if sum(count) > N:\n",
    "        break\n",
    "\n",
    "tree = list()\n",
    "\n",
    "for value in count:\n",
    "    \n",
    "    tmp = nums[:value]\n",
    "    tree.append(tmp)\n",
    "    for num in tmp:\n",
    "        nums.remove(num)\n",
    "    \n",
    "results = [sum(col) for col in tree]\n",
    "\n",
    "print(results.index(max(results)) + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70ac919f",
   "metadata": {},
   "source": [
    "### 等差数列"
   ]
  },
  {
   "cell_type": "raw",
   "id": "db6a3a3c",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一\n",
    "部分的数列，只记得其中 N 个整数。\n",
    "现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有\n",
    "几项？\n",
    "【输入格式】\n",
    "输入的第一行包含一个整数 N。\n",
    "第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数\n",
    "列中的顺序给出)\n",
    "【输出格式】\n",
    "输出一个整数表示答案。\n",
    "【样例输入】\n",
    "5\n",
    "2 6 4 10 20\n",
    "【样例输出】\n",
    "10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "aa4241b7",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "2 6 4 10 20\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "N = int(input())\n",
    "\n",
    "nums = list(map(int, input().split()))\n",
    "\n",
    "nums.sort()\n",
    "\n",
    "sep = 0\n",
    "for i in range(len(nums) - 2):\n",
    "    if nums[i] - nums[i+1] == nums[i+1] - nums[i+2]:\n",
    "        sep = nums[i+1] - nums[i]\n",
    "        break\n",
    "\n",
    "results = list()\n",
    "for value in range(nums[0], nums[-1]+1, sep):\n",
    "    results.append(value)\n",
    "    \n",
    "print(len(results))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99636ba1",
   "metadata": {},
   "source": [
    "### 后缀表达式"
   ]
  },
  {
   "cell_type": "raw",
   "id": "f9ecfe5a",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1, A2, · · · , AN+M+1，小\n",
    "明想知道在所有由这 N 个加号、M 个减号以及 N + M + 1 个整数凑出的合法的\n",
    "后缀表达式中，结果最大的是哪一个？\n",
    "请你输出这个最大的结果。\n",
    "例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。\n",
    "【输入格式】\n",
    "第一行包含两个整数 N 和 M。\n",
    "第二行包含 N + M + 1 个整数 A1, A2, · · · , AN+M+1。\n",
    "【输出格式】\n",
    "输出一个整数，代表答案。\n",
    "【样例输入】\n",
    "1 1\n",
    "1 2 3\n",
    "【样例输出】\n",
    "4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "67c43123",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "1 2 3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "N, M = map(int, input().split())\n",
    "\n",
    "nums = list(map(int, input().split()))\n",
    "\n",
    "nums.sort(reverse=True)\n",
    "count = 0\n",
    "result = nums[0]\n",
    "for num in nums[1:]:    \n",
    "    if count < N:\n",
    "        result += num\n",
    "    else:\n",
    "        result -= num\n",
    "    count += 1\n",
    "    \n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fdf0020",
   "metadata": {},
   "source": [
    "### 灵能传输"
   ]
  },
  {
   "cell_type": "raw",
   "id": "c6ccd916",
   "metadata": {},
   "source": [
    "【题目背景】\n",
    "在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在\n",
    "游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对\n",
    "一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的\n",
    "刺蛇飞龙等低血量单位。\n",
    "【问题描述】\n",
    "你控制着 n 名高阶圣堂武士，方便起见标为 1, 2, · · · , n。每名高阶圣堂武士\n",
    "需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai\n",
    "非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这\n",
    "名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。现在系统赋予了\n",
    "你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i ∈ [2, n − 1]，若\n",
    "ai ≥ 0 则其两旁的高阶圣堂武士，也就是 i − 1、i + 1 这两名高阶圣堂武士会从\n",
    "i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai < 0 则其两旁的高阶圣堂武士，\n",
    "也就是 i − 1, i + 1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。形\n",
    "式化来讲就是 ai−1+ = ai, ai+1+ = ai, ai− = 2ai。\n",
    "灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂\n",
    "武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为\n",
    "maxni=1|ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武\n",
    "士的不稳定度最小。\n",
    "【输入格式】\n",
    "本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。\n",
    "接下来依次输入每一组询问。\n",
    "每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。\n",
    "接下来一行包含 n 个数 a1, a2, · · · , an。\n",
    "试题 J: 灵能传输 15\n",
    "第十届蓝桥杯大赛软件类省赛C/C++大学B组\n",
    "【输出格式】\n",
    "输出 T 行。每行一个整数依次表示每组询问的答案。\n",
    "【样例输入】\n",
    "33\n",
    "5 -2 3\n",
    "4\n",
    "0 0 0 0\n",
    "3\n",
    "1 2 3\n",
    "【样例输出】\n",
    "303\n",
    "【样例说明】\n",
    "对于第一组询问：\n",
    "对 2 号高阶圣堂武士进行传输操作后 a1 = 3，a2 = 2，a3 = 1。答案为 3。\n",
    "对于第二组询问：\n",
    "这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。\n",
    "【样例输入】\n",
    "34\n",
    "-1 -2 -3 7\n",
    "4\n",
    "2 3 4 -8\n",
    "5\n",
    "-1 -1 6 -1 -1\n",
    "试题J: 灵能传输 16\n",
    "第十届蓝桥杯大赛软件类省赛 C/C++ 大学 B 组\n",
    "【样例输出】\n",
    "574\n",
    "【样例输入】\n",
    "见文件trans3.in。\n",
    "【样例输出】\n",
    "见文件trans3.ans。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "lanqiaobei",
   "language": "python",
   "name": "lanqiaobei"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
